package 我的Java学习_算法基础.day_05;

public class _081_字符串匹配之RabinKarp_下 {
    public static void main(String[] args) {
        String s ="ABABAB";
        String key = "AB";
        match(key,s);
    }
    //滚动hash
    static int seed = 31;
    static void match(String key,String s){
        long hash_key=hash(key);
        long[] hash_s = hash(s,key.length());
        match(hash_key,hash_s);
    }
    static void match(long hash_p,long[] hash_s){
        for(int i =0;i<hash_s.length;i++){
            if(hash_p==hash_s[i]){
                System.out.println("match:"+i);
            }
        }
    }
    static long[] hash(final String s,final int n){
        long[] res = new long[s.length()-n+1];
        //前m个字符的hash
        res[0] = hash(s.substring(0,n));
        for(int i =n;i<s.length();i++){
            char newChar = s.charAt(i);
            char oldChar = s.charAt(i-n);
            //前n个字符串的hash*seed~前n字符的第一字符*seed的n次方
            long v = (res[i-n]*seed+newChar-XN(seed,n)*oldChar)%Long.MAX_VALUE;
            res[i-n+1] = v;
        }
        return res;
    }

    private static long XN(int x, int n) {
        while(n>1){
            x*=x;
            n--;
        }
        return x;
    }

    static long hash(String s){
        long hash = 0;
        for(int i = 0;i<s.length();i++){
            hash=hash*seed+s.charAt(i);
        }
        return hash%Long.MAX_VALUE;
    }
}
